class NQueensWithBite(object):

    def __init__(self):
        self.count = 0

    def totalNQueens(self, n):
        if n < 1:
            return []
        self.DFS(n, 0, 0, 0, 0)
        return self.count

    def DFS(self, n, row, cols, pie, na):
        if row >= n:
            self.count += 1
            return
        bits = (~(cols | pie | na)) & ((1 << n) - 1)  # 得到当前左右空位

        while bits:
            p = bits & -bits  # 取到最低位的1
            self.DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)
            bits = bits & (bits - 1)  # 去掉最低位的1


if __name__ == '__main__':
    queen = NQueensWithBite()
    res = queen.totalNQueens(4)
    print(res)
